home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / fax / src / util / Array.h < prev    next >
C/C++ Source or Header  |  1994-08-01  |  12KB  |  349 lines
  1. /*    $Header: /usr/people/sam/fax/util/RCS/Array.h,v 1.9 1994/02/28 14:23:42 sam Rel $ */
  2. /*
  3.  * Copyright (c) 1990, 1991, 1992, 1993, 1994 Sam Leffler
  4.  * Copyright (c) 1991, 1992, 1993, 1994 Silicon Graphics, Inc.
  5.  *
  6.  * Permission to use, copy, modify, distribute, and sell this software and 
  7.  * its documentation for any purpose is hereby granted without fee, provided
  8.  * that (i) the above copyright notices and this permission notice appear in
  9.  * all copies of the software and related documentation, and (ii) the names of
  10.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  11.  * publicity relating to the software without the specific, prior written
  12.  * permission of Sam Leffler and Silicon Graphics.
  13.  * 
  14.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  15.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  16.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  17.  * 
  18.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  19.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  20.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  21.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  22.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  23.  * OF THIS SOFTWARE.
  24.  */
  25. #ifndef _Array_
  26. #define _Array_
  27. // $Revision: 1.9 $
  28. // $Date: 1994/02/28 14:23:42 $
  29. #include "Obj.h"
  30. #include "Ptr.h"
  31.  
  32. // Here's what the declaration of an array class looks like to the user:
  33. /*
  34. class ARRAY<ITEM> : public fxArray {
  35. public:
  36.     ARRAY();
  37.     ARRAY(u_int size);
  38.     ARRAY(ARRAY const &);
  39.     void operator=(ARRAY const &);
  40.     ITEM const & operator[](u_int index) const;
  41.     u_int length() const;
  42.     void append(ITEM const & item);
  43.     void append(ARRAY const & a);
  44.     void remove(u_int start, u_int leng=1);
  45.     ARRAY cut(u_int start, u_int leng=1);
  46.     void insert(ITEM const & item, u_int p);
  47.     void insert(ARRAY const & a, u_int posn);
  48.     void resize(u_int length);
  49.     ARRAY extract(u_int start, u_int len);
  50.     void head(u_int len);
  51.     void tail(u_int len);
  52.     u_int find(ITEM const & item) const;
  53.     void qsort(u_int start, u_int len);
  54.     void swap(u_int,u_int);
  55.  
  56. protected:
  57.     virtual void getmem();
  58.     virtual void expand();
  59.     virtual void createElements(void*, u_int numbytes);
  60.     virtual void destroyElements(void*, u_int numbytes);
  61.     virtual void copyElements(void const *src, void *dst, u_int numbytes);
  62.     virtual int compareElements(void const *elem1, void const *elem2);
  63. };
  64. */
  65.  
  66. //
  67. // There are three flavors of arrays:
  68. //   struct Arrays (in which the contents of the elements are not looked at)
  69. //   pointer Arrays (the elements are pointers to some memory)
  70. //   object Arrays (the elements are objects, which must be constructed and
  71. //    destructed)
  72. //
  73. // Macros exist for each of these fxArray flavors:
  74. //   fxDECLARE_Array (same as fxDECLARE_StructArray)
  75. //   fxDECLARE_PtrArray
  76. //      (acts like fxDECLARE_Array, except that pointers are
  77. //       initialized to nil when new elements are added)
  78. //   fxDECLARE_ObjArray
  79.  
  80. static const u_int fx_invalidArrayIndex = (u_int) -1;
  81.  
  82. class fxArray : public fxObj {
  83. public:
  84.     u_int length() const;
  85.     u_int elementSize() const
  86.     { return elementsize; }
  87.     void resize(u_int length);
  88.     void setMaxLength(u_int maxlength);
  89.     void qsort(u_int posn, u_int len);
  90.     void qsort();
  91.  
  92.     void swap(u_int,u_int);
  93.  
  94.     virtual char const *className() const = 0;
  95.  
  96. protected:
  97.     class fxAddress {
  98.     public:
  99.     fxAddress()                    { ptr = 0; }
  100.     fxAddress(void* p)                { ptr = (char*) p; }
  101.     fxAddress operator+(u_long offset) const    { return ptr + offset; }
  102.     fxBool operator==(const fxAddress& r) const    { return ptr == r.ptr; }
  103.     fxBool operator!=(const fxAddress& r) const    { return ptr != r.ptr; }
  104.     // NB: operator const void*() const does not work
  105.     operator void*() const                { return ptr; }
  106.     protected:
  107.     char* ptr;
  108.     };
  109.  
  110.     fxArray(u_short esize, u_int initlength=0);
  111.     fxArray(u_int esize, u_int num, void *data);
  112.     fxArray(fxArray const &);
  113.     virtual ~fxArray();
  114.  
  115.     void * operator[](u_int index) { return data + elementsize*index; }
  116.     void operator=(fxArray const &);
  117.  
  118.     void append(void const *item);
  119.     void append(fxArray const &);
  120.     void remove(u_int start, u_int length=1);
  121.     void insert(fxArray const &, u_int posn);
  122.     void insert(void const *item, u_int posn);
  123.  
  124.     u_int find(void const *, u_int start=0) const;
  125.  
  126.     // The objects in the array are stored sequentially at the
  127.     // location pointed to by data. The length of the known
  128.     // allocated segment is stored in maxi, in bytes. The
  129.     // length of the array is stored in num, in *bytes*. The
  130.     // size of an array element is stored in elementsize, in bytes.
  131.  
  132.     // data is allowed to be nil iff (maxi==0)
  133.     fxAddress data;
  134.  
  135.     // num <= maxi
  136.     u_int maxi,num;
  137.     u_short elementsize;
  138.  
  139.     // These two methods control how the array class goes to
  140.     // fetch more memory.
  141.     virtual void getmem();
  142.     virtual void expand();
  143.  
  144.     // The raw methods are used to
  145.     // implement methods which return an fxArray type.
  146.     void * raw_copy() const;
  147.     void * raw_extract(u_int start, u_int length) const;
  148.     void * raw_cut(u_int start, u_int length);
  149.     void * raw_head(u_int) const;
  150.     void * raw_tail(u_int) const;
  151.  
  152.     void qsortInternal(u_int, u_int, void *);
  153.     void destroy();
  154.  
  155.     // These three methods can be overridden to properly copy, delete,
  156.     // and create new array elements in the desired manner. By default
  157.     // `create' and `destroy' do nothing, and `copy' is a simple bcopy.
  158.     //
  159.     // The job of create is to take an area of uninitialized memory and
  160.     // create a series of valid objects in it. The job of destroy is to
  161.     // take a series of valid objects and destroy any resources they
  162.     // consume. The status of the memory after the destroy is irrelevant.
  163.     // The job of copy is to take a source array of objects, and copy
  164.     // them to an area of *uninitialized* memory. There will not be any
  165.     // objects stored there previous to the copy.
  166.     virtual void createElements(void *, u_int numbytes);
  167.     virtual void destroyElements(void *, u_int numbytes);
  168.     virtual void copyElements(void const *src, void *dst, u_int numbytes)
  169.     const;
  170.     virtual int compareElements(void const *, void const *) const;
  171. };
  172.  
  173. #define fxArrayHeader(ARRAY,ITEM)                    \
  174.     ARRAY();                                \
  175.     ARRAY(u_int size);                            \
  176.     ARRAY(ARRAY const&a);                        \
  177.     ~ARRAY();                                \
  178.     virtual const char* className() const;                \
  179.     void operator=(ARRAY const&a) {                    \
  180.     maxi = a.maxi; num = a.num; if (data) delete (void*)data;    \
  181.     data = a.raw_copy(); }                        \
  182.     ITEM & const operator[](u_int index) const {            \
  183.       fxAssert(index*sizeof(ITEM) < num, "Invalid Array[] index");    \
  184.       return *(ITEM *)((char *)((void *)data) + index*sizeof(ITEM));    \
  185.     }                                    \
  186.     void append(ITEM const & item) { fxArray::append(&item); }        \
  187.     void append(ARRAY const & a) { fxArray::append(a); }        \
  188.     void remove(u_int start, u_int length=1)                \
  189.     { fxArray::remove(start,length); }                \
  190.     ARRAY cut(u_int start, u_int len = 1);                \
  191.     void insert(ARRAY const & a, u_int p)                \
  192.     { fxArray::insert(a,p); }                    \
  193.     void insert(ITEM const & item, u_int p)                \
  194.     { fxArray::insert(&item,p);}                    \
  195.     ARRAY extract(u_int start, u_int len);                \
  196.     ARRAY head(u_int len = 1);                        \
  197.     ARRAY tail(u_int len = 1);                        \
  198.     int find(ITEM const& x, u_int start=0) const {            \
  199.     return fxArray::find(&x,start);                    \
  200.     }                                    \
  201. protected:                                \
  202.     ARRAY(u_int esize, u_int num, void *data);                \
  203. public:                                    \
  204. __enddef__
  205.  
  206. #define fxArrayVirtuals                            \
  207. protected:                                \
  208.     virtual void createElements(void *,u_int);                \
  209.     virtual void destroyElements(void *,u_int);                \
  210.     virtual void copyElements(void const*,void*,u_int) const;        \
  211.     virtual int compareElements(void const *, void const *) const;      \
  212. __enddef__
  213.  
  214.  
  215. //----------------------------------------------------------------------
  216. // Declare an array containing items of type ITEM.
  217.  
  218. #define fxDECLARE_Array(ARRAY,ITEM)                    \
  219. class ARRAY : public fxArray {                        \
  220. public:                                    \
  221.     fxArrayHeader(ARRAY,ITEM)                        \
  222. };                                    \
  223. fxDECLARE_Ptr(ARRAY);                            \
  224. __enddef__
  225.  
  226. #define fxDECLARE_StructArray(ARRAY,ITEM) fxDECLARE_Array(ARRAY,ITEM)
  227. #define fxDECLARE_PrimArray(ARRAY,ITEM)    fxDECLARE_Array(ARRAY,ITEM)
  228.  
  229. #define fxDECLARE_ObjArray(ARRAY,ITEM)                    \
  230. class ARRAY : public fxArray {                        \
  231. public:                                    \
  232.     fxArrayHeader(ARRAY,ITEM)                        \
  233.     fxArrayVirtuals                            \
  234. };                                    \
  235. fxDECLARE_Ptr(ARRAY);                            \
  236. __enddef__
  237.  
  238. #define fxDECLARE_PtrArray(ARRAY, POINTER)                \
  239. class ARRAY : public fxArray {                        \
  240. public:                                    \
  241.     fxArrayHeader(ARRAY,POINTER)                    \
  242. protected:                                \
  243.     virtual void createElements(void *, u_int);                \
  244. };                                    \
  245. fxDECLARE_Ptr(ARRAY);                            \
  246. __enddef__
  247.  
  248. //----------------------------------------------------------------------
  249. // Various method implementations
  250.  
  251. #define fxIMPLEMENT_ArrayMethods(ARRAY,ITEM)                \
  252.     ARRAY::ARRAY() : fxArray(sizeof(ITEM))                \
  253.     { if (data) createElements(data,num); }                \
  254.     ARRAY::ARRAY(ARRAY const& a) : fxArray(a.elementsize)         \
  255.     { maxi = a.maxi; num = a.num; data = a.raw_copy(); }        \
  256.     ARRAY::ARRAY(u_int size) : fxArray(sizeof(ITEM),size)        \
  257.     { createElements(data,num); }                    \
  258.     ARRAY::~ARRAY() { destroy(); }                    \
  259.     const char* ARRAY::className() const { return fxQUOTE(ARRAY); }    \
  260.     ARRAY ARRAY::cut(u_int start, u_int len)                \
  261.     {return ARRAY(sizeof(ITEM), len*sizeof(ITEM),raw_cut(start,len));}\
  262.     ARRAY ARRAY::extract(u_int start, u_int len)            \
  263.     {return ARRAY(sizeof(ITEM), len*sizeof(ITEM),raw_extract(start,len));}\
  264.     ARRAY ARRAY::head(u_int len)                    \
  265.     {return ARRAY(sizeof(ITEM), len*sizeof(ITEM),raw_head(len));}   \
  266.     ARRAY ARRAY::tail(u_int len)                    \
  267.         {return ARRAY(sizeof(ITEM),len*sizeof(ITEM),raw_tail(len));}    \
  268.     ARRAY::ARRAY(u_int esize, u_int num, void * data)                \
  269.     : fxArray(esize,num,data) {}                    \
  270. __enddef__
  271.  
  272. #define fxIMPLEMENT_ObjArrayMethods(ARRAY,ITEM)                \
  273.     void ARRAY::createElements(void * start, u_int numbytes) {        \
  274.     ITEM * ptr = (ITEM *)start;                    \
  275.     for (;;) {                            \
  276.         if (numbytes == 0) break;                    \
  277.         numbytes -= elementsize;                    \
  278.         ITEM * obj = fxNEW(ptr) ITEM;                \
  279.         ptr++;                             \
  280.     }                                \
  281.     }                                    \
  282.     void ARRAY::destroyElements(void * start, u_int numbytes) {        \
  283.     ITEM * ptr = (ITEM *)start;                    \
  284.     while (numbytes) {                        \
  285.         numbytes -= elementsize;                    \
  286.         ptr->ITEM::~ITEM();                        \
  287.         ptr++;                            \
  288.     }                                \
  289.     }                                    \
  290.     void ARRAY::copyElements(void const * src, void * dst,        \
  291.         u_int numbytes) const {                    \
  292.     if (src<dst) {                            \
  293.         src = (const char*)src + numbytes;                \
  294.         dst = (char*)dst + numbytes;                \
  295.         const ITEM * p = (const ITEM *)src - 1;            \
  296.         ITEM * q = (ITEM *)dst - 1;                    \
  297.         while (numbytes > 0) {                    \
  298.         ITEM * obj = fxNEW(q) ITEM(*p);                \
  299.         q--; p--;                        \
  300.         numbytes -= elementsize;                \
  301.         }                                \
  302.     } else {                            \
  303.         const ITEM * p = (const ITEM *)src;                \
  304.         ITEM * q = (ITEM *)dst;                    \
  305.         while (numbytes > 0) {                    \
  306.         ITEM * obj = fxNEW(q) ITEM(*p);                \
  307.         q++; p++;                        \
  308.         numbytes -= elementsize;                \
  309.         }                                \
  310.     }                                \
  311.     }                                    \
  312.     int ARRAY::compareElements(void const *o1, void const *o2) const    \
  313.     {                                    \
  314.     return ((const ITEM *)o1)->compare((const ITEM *)o2);        \
  315.     }                                    \
  316. __enddef__
  317.  
  318. #define fxIMPLEMENT_PtrArrayMethods(ARRAY,POINTER)            \
  319.     void ARRAY::createElements(void * start, u_int numbytes) {        \
  320.     memset(start,0,numbytes);                    \
  321.     }                                    \
  322. __enddef__
  323.  
  324. //----------------------------------------------------------------------
  325. // Implement various types of arrays
  326.  
  327. #define fxIMPLEMENT_Array(ARRAY,ITEM)                    \
  328.     fxIMPLEMENT_ArrayMethods(ARRAY,ITEM)                \
  329. __enddef__
  330.  
  331. #define fxIMPLEMENT_PrimArray(ARRAY,ITEM)                \
  332.     fxIMPLEMENT_ArrayMethods(ARRAY,ITEM)                \
  333. __enddef__
  334.  
  335. #define fxIMPLEMENT_StructArray(ARRAY,ITEM)                 \
  336.     fxIMPLEMENT_ArrayMethods(ARRAY,ITEM)                \
  337. __enddef__
  338.  
  339. #define fxIMPLEMENT_ObjArray(ARRAY,ITEM)                \
  340.     fxIMPLEMENT_ArrayMethods(ARRAY,ITEM)                \
  341.     fxIMPLEMENT_ObjArrayMethods(ARRAY,ITEM)                \
  342. __enddef__
  343.  
  344. #define fxIMPLEMENT_PtrArray(ARRAY,POINTER)                \
  345.     fxIMPLEMENT_Array(ARRAY,POINTER)                    \
  346.     fxIMPLEMENT_PtrArrayMethods(ARRAY,POINTER)                \
  347. __enddef__
  348. #endif /* _ARRAY_ */
  349.